package codingforgreat.class17;


//lc:lcr 097
public class Class04_DistinctSubseq {
    public static int dp(String S, String T) {
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        int N = s.length;
        int M = t.length;
        int[][] dp = new int[N][M];
        //dp[0][j] = 0 s拿前0个字符组成T前j个字符
        //dp[i][0] = S[i] == T[0] ? 1 : 0  s拿前i个字符组成T前0个字符
        dp[0][0] = s[0] == t[0] ? 1 : 0;
        for (int i = 1; i < N; i++) {
            dp[i][0] = s[i] == t[0] ? (dp[i - 1][0] + 1) : dp[i - 1][0];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i][j] = dp[i - 1][j];
                if(s[i] == t[j]){
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[N - 1][M - 1];
        }
    public static int numDistinct3(String S, String T) {
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        int[] dp = new int[t.length + 1];
        dp[0] = 1;
        for (int j = 1; j <= t.length; j++) {
            dp[j] = 0;
        }
        for (int i = 1; i <= s.length; i++) {
            for (int j = t.length; j >= 1; j--) {
                dp[j] += s[i - 1] == t[j - 1] ? dp[j - 1] : 0;
            }
        }
        return dp[t.length];
    }


    public static void main(String[] args) {
        String S = "1212311112121132";
        String T = "13";

        System.out.println(numDistinct3(S, T));
        System.out.println(dp(S, T));

    }
}
